/*
 * @lc app=leetcode.cn id=878 lang=cpp
 *
 * [878] 第 N 个神奇数字
 */

// @lc code=start
class Solution {
public:
    int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); };
    int lcm(int a, int b) { return (a * b) / gcd(a, b); }
    long long magicNumber(long long n, int a, int b) {
        return (n / a + n / b - n / (lcm(a, b)));
    }
    int nthMagicalNumber(int n, int a, int b) {
        int mod = 1e9 + 7;
        long long l = 1;
        long long r = (long long)n * min(a, b);
        long long mid;
        while (l < r) {
            mid = l + (r - l) / 2;
            if (magicNumber(mid, a, b) < n) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return l % mod;
    };
};
// @lc code=end
